# Q: Given two strings, determine if all the characters in the second string
# appear in the first string; thus, DA is a subset of ABCD. Counts matter, so
# DAD is not a subset of ABCD, since there are two D in the second string but
# only one D in the first string. You may assume that the second string is no
# longer than the first string.
#
# A: Naive solution would be, for each character in second string, find it in
# the first string. If found, then remove it and repeat until all characters in
# second string are exhausted. This will take O(mn) where m and n are the length
# of the strings and it needs to rescan the first string as many times as the
# number of characters in second string.
# 
# The better solution is to use hash map or array initialized with count of how
# many times each character appears in the first string. Then for each character
# in second string, find the character in the hash/array. If found, decrement
# the count. This will take O(m+n) time.

def naive_string_subset(str1, str2):
   str1array = list(str1)
   for c2 in str2:
      found = False
      for i in range(0, len(str1array)):
         if c2 == str1array[i]:
            found = True
            del str1array[i]
            break
      if not found:
         return False
   return True

def better_string_subset(str1, str2):
   cmap = { }
   for c in str1:
      cmap[c] = cmap.get(c, 0) + 1

   for c in str2:
      cnt = cmap.get(c)
      if cnt == None or cnt - 1 < 0:
         return False
      cmap[c] = cnt - 1
   return True

assert naive_string_subset('ABCD', 'DA') == better_string_subset('ABCD', 'DA')
assert naive_string_subset('ABCD', 'DAD') == better_string_subset('ABCD', 'DAD')

